package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list'>扁平化多级双向链表(Flatten a Multilevel Doubly Linked List)</a>
 * <p>
 * 你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。
 * 这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。
 * 这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。
 * </p>
 * <p>
 * 给定链表的头节点 head ，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。
 * 子列表中的节点应该出现在扁平化列表中的 curr 之后 和 curr.next 之前 。
 * </p>
 * <p>返回 扁平列表的 head 。列表中的节点必须将其 所有 子指针设置为 null 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * <a href='https://leetcode.cn/problems/flatten-a-multilevel-doubly-linked-list/'>查看示例</a>
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>节点数目不超过 1000</li>
 *         <li>1 <= Node.val <= 10^5</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0114FlattenBinaryTreeToLinkedList_M 二叉树展开为链表(Flatten Binary Tree to Linked List)
 * @see LC0430FlattenMultilevelDoublyLinkedList_M 扁平化多级双向链表(Flatten a Multilevel Doubly Linked List)
 * @since 2024/8/22 11:05
 */
public class LC0430FlattenMultilevelDoublyLinkedList_M {
    static class Solution {
        public Node flatten(Node head) {
            Node currNode = head;
            while (currNode != null) {
                if (currNode.child != null) {
                    // 如果当前节点既有child节点，也有next节点。让next节点挂到child节点的尾节点后面
                    /*
                        例如：
                            1->2->3->4->5->6            1->2->3                     1->2->3->7->8->4->5->6
                                  |                 ==>       |                 ==>          |
                                  7->8                        7->8->4->5->6                  9
                                  |                           |
                                  9                           9
                     */
                    if (currNode.next != null) {
                        // 找到currNode.child的尾节点childTail
                        Node childTail = currNode.child;
                        while (childTail.next != null) {
                            childTail = childTail.next;
                        }
                        // 使当前节点的next节点，挂到childTail的next
                        childTail.next = currNode.next;
                        currNode.next.prev = childTail;
                    }
                    // 让子节点成为currNode.next节点；并置空currNode.child节点
                    currNode.next = currNode.child;
                    currNode.child.prev = currNode;
                    // 将子节点置空
                    currNode.child = null;
                }
                currNode = currNode.next;
            }
            return head;
        }

        public Node flatten2(Node head) {
            Node currNode = head;
            while (currNode != null) {
                if (currNode.child != null) {
                    // 扁平化子节点，返回扁平化链表的头
                    Node flattenChildrenHead = flatten(currNode.child);
                    // 找到扁平化子节点的尾节点
                    Node flattenChildrenTail = flattenChildrenHead;
                    while (flattenChildrenTail.next != null) {
                        flattenChildrenTail = flattenChildrenTail.next;
                    }
                    // 将当前节点的next节点(如果有)，挂到扁平化链表的next
                    if (currNode.next != null) {
                        flattenChildrenTail.next = currNode.next;
                        currNode.next.prev = flattenChildrenTail;
                    }
                    // 将扁平化链表挂到当前节点的next
                    currNode.next = flattenChildrenHead;
                    flattenChildrenHead.prev = currNode;
                    // 将子节点置空
                    currNode.child = null;
                }
                currNode = currNode.next;
            }
            return head;
        }


        private static class Node {
            public int val;
            public Node prev;
            public Node next;
            public Node child;
        }
    }


    public static void main(String[] args) {
        Solution.Node node1 = new Solution.Node();
        Solution.Node node2 = new Solution.Node();
        Solution.Node node3 = new Solution.Node();
        Solution.Node node4 = new Solution.Node();
        Solution.Node node5 = new Solution.Node();
        Solution.Node node6 = new Solution.Node();
        Solution.Node node7 = new Solution.Node();
        Solution.Node node8 = new Solution.Node();
        Solution.Node node9 = new Solution.Node();
        Solution.Node node10 = new Solution.Node();
        Solution.Node node11 = new Solution.Node();
        Solution.Node node12 = new Solution.Node();
        node1.val = 1;
        node2.val = 2;
        node3.val = 3;
        node4.val = 4;
        node5.val = 5;
        node6.val = 6;
        node7.val = 7;
        node8.val = 8;
        node9.val = 9;
        node10.val = 10;
        node11.val = 11;
        node12.val = 12;
        node1.next = node2;
        node2.prev = node1;
        node2.next = node3;
        node3.prev = node2;
        node3.next = node4;
        node3.child = node7;
        node4.prev = node3;
        node4.next = node5;
        node5.prev = node4;
        node5.next = node6;
        node6.prev = node5;
        node6.next = null;
        node7.next = node8;
        node8.prev = node7;
        node8.next = node9;
        node8.child = node11;
        node9.prev = node8;
        node9.next = node10;
        node10.prev = node9;
        node11.next = node12;
        node12.prev = node11;

        Solution solution = new Solution();
        Solution.Node flatten = solution.flatten(node1);
        while (flatten != null) {
            System.out.println(flatten.val);
            flatten = flatten.next;
        }
    }
}